// https://leetcode.cn/problems/product-of-array-except-self/
// Created by ade on 2022/9/9.
// 时间复杂度O(N), 不准用除法
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    // 空间复杂度O(N)
    vector<int> productExceptSelf1(vector<int> &nums) {
        int len = nums.size();
        vector<int> left(len, 1);
        vector<int> right(len, 1);
        for (int i = 1; i < len; i++) {
            left[i] = nums[i - 1] * left[i - 1];
            right[len - i - 1] = nums[len - i] * right[len - i];
        }
        vector<int> res(len, 1);
        for (int i = 0; i < len; i++) {
            res[i] = left[i] * right[i];
        }
        return res;
    }

    // 空间复杂度O(1)
    vector<int> productExceptSelf(vector<int> &nums) {
        int len = nums.size();
        vector<int> res(len, 1);
        for (int i = 1; i < len; i++) {
            res[i] = nums[i - 1] * res[i - 1];
        }
        int R = 1;
        for (int i = len - 1; i >= 0; i--) {
            res[i] = res[i] * R;
            R *= nums[i];
        }
        return res;
    }
};


int main() {
    Solution so;
    vector<int> nums = {1, 2, 3, 4, 5};
    auto res = so.productExceptSelf(nums);
    for (auto i:res) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}